#include <stdio.h>
#include <stdlib.h>
typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;

void merge(List la,List lb);
void main()
{
	List La, Lb;
	Node *p, *q;
	int i;

	La = (List)malloc(sizeof(Node));
	p = La;
	Lb = (List)malloc(sizeof(Node));
	q = Lb;

	for(i= 1; i<=10;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));
		p->next->d = 2 *i;
		p->next->next = NULL;
		p = p->next;

		q->next = (Node *)malloc(sizeof(Node));
		q->next->d = 3*i -2;
		q->next->next = NULL;
		q = q->next;
	}
	merge(La,Lb);
	p = La->next;
	//printf("\n\n\n");
	while(p!=NULL)
	{
		printf(" %d   ", p->d);
		p = p->next;
	}
	printf("\n");
}


void merge(List la,List lb){
	Node *pa,*pb,*pre,*s;
	pa =la->next;//pa初始化为la的第一个元素
	pb=lb->next;//pb初始化为lb的第一个元素
	pre=la;//pre 放在la上,作为修改指针使用
	while(pb!=NULL){
		//相等就同时往后移动
		if(pa!=NULL&&pa->d ==pb->d){
			pre = pa;
			pa=pa->next;
			pb=pb->next;
			continue;
		}
		//a小就a向后移动
		if(pa!=NULL&&pa->d<pb->d){
			pre=pa;
			pa=pa->next;
			continue;
		}
		//b小
		if(pa!=NULL&&pa->d>pb->d){
			s=(Node*)malloc(sizeof(Node));//s用于存储新申请的节点地址
			s->d=pb->d;
			//执行一次插入操作
			s->next=pa;
			pre->next=s;
			pre=s;
			pb=pb->next;
			continue;
		}

		if(pa==NULL){
			pre->next=pb;//将a的最后一个元素连接在b后
			break;
		}
	}


}


/*
设计一个函数
	void merge(List La, List Lb)
其功能是将Lb合并到La中，其中La和Lb的元素均为严格递增有序排列，且合并后的La的元素也为非递减有序排列。
其中List是如下结构体：
typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;

当执行如下的main函数后
void main()
{
	List La, Lb;
	Node *p, *q;
	int i;

	La = (List)malloc(sizeof(Node));
	p = La;
	Lb = (List)malloc(sizeof(Node));
	q = Lb;

	for(i= 1; i<=10;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));
		p->next->d = 2 *i;
		p->next->next = NULL;
		p = p->next;

		q->next = (Node *)malloc(sizeof(Node));
		q->next->d = 3*i -2;
		q->next->next = NULL;
		q = q->next;
	}
	merge(La,Lb);
	p = La->next;
	//printf("\n\n\n");
	while(p!=NULL)
	{
		printf(" %d   ", p->d);
		p = p->next;
	}
	printf("\n");
}
执行的结果为
1    2    4    6    7    8    10    12    13    14    16    18    19    20    22    25    28
*/